package com.example.shardingspheredemo;

import org.mybatis.spring.annotation.MapperScan;
import org.springframework.boot.SpringApplication;
import org.springframework.boot.autoconfigure.SpringBootApplication;
import org.springframework.boot.autoconfigure.jdbc.DataSourceAutoConfiguration;

import java.util.Arrays;
import java.util.Random;

@SpringBootApplication
//@SpringBootApplication(exclude = DataSourceAutoConfiguration.class)
@MapperScan("com.example.shardingspheredemo.model.t.mapper")
public class ShardingSphereDemoApplication {

    public static void main(String[] args) {
        SpringApplication.run(ShardingSphereDemoApplication.class, args);
    }

    public static int swapCount = 0;

    public static void main2(String[] args) {
        int maxValue = 1000;
        int count = 1000;
        int[] arrays = new int[count];
        for (int i = 0; i < arrays.length; i++) {
            arrays[i] = (int) (Math.random() * maxValue);
        }
//        int[] arrays = new int[]{29, 10, 14, 37, 20, 25, 44, 15};
        System.out.println("arrays before is =" + Arrays.toString(arrays));
        long startTime = System.currentTimeMillis();
        doQuickSort(arrays, 0, arrays.length - 1);
        long endTime = System.currentTimeMillis();
        System.out.println("endTime-startTime=" + (endTime - startTime) + "swapCount=" + swapCount);
    }

    private static int partition(int[] array, int i, int j) {
        int randomIndex = i + new Random().nextInt(j - i);
        swap(array, i, randomIndex);
        //选择最左侧的元素作为中心点,middleValue就是中心点的值
        int middleValue = array[i];
        int middleIndex = i;
        //从i+1遍历整个数组
        for (int k = i + 1; k <= j; k++) {
            //如果数组元素小于middleValue，表示middleIndex需要右移一位
            //右移之后，我们需要将小于middleValue的array[k]移动到middleIndex的左边，
            // 最简单的办法就是交换k和middleIndex的值
            if (array[k] < middleValue) {
                middleIndex++;
                //交换数组的两个元素
                swap(array, k, middleIndex);
            } //如果数组元素大于等于middleValue,则继续向后遍历,middleIndex值不变
        }
        // 最后将中心点放入middleIndex位置
        swap(array, i, middleIndex);
//        System.out.println("array=" + Arrays.toString(array));
        return middleIndex;
    }

    public static void doQuickSort(int[] array, int low, int high) {
        //递归的结束条件
        if (low < high) {
            //找出中心节点的值
            int middleIndex = partition(array, low, high);
            //数组分成了三部分：
            // a[low..high] ~> a[low..m–1], pivot, a[m+1..high]
            //递归遍历左侧部分
            doQuickSort(array, low, middleIndex - 1);
            // a[m] 是中心节点，已经排好序了，不需要继续遍历
            //递归遍历右侧部分
            doQuickSort(array, middleIndex + 1, high);
            System.out.println("QuickSort之后的数组=" + Arrays.toString(array));
        }
    }

    private static void swap(int[] array, int i, int j) {
        if (i == j) {
            return;
        }
        array[i] = array[i] ^ array[j];
        array[j] = array[i] ^ array[j];
        array[i] = array[i] ^ array[j];
        swapCount++;
    }

}
